#include<vector>
#include<string>
#include<unordered_map>
#include<algorithm>
using namespace std;
class Solution {
    int GCA(int n, int m) {
        if (n < m)swap(n, m);
        while (m != 0) {
            int tmp = n % m;
            n = m;
            m = tmp;
        }
        return n;
    }
    string getKey(int i, int j) {
        return  to_string(i) + " " + to_string(j);
    }

public:
    vector<int> bestLine(vector<vector<int>>& points) {
        //start,end,cnt
        vector<int>res = { 0,0,1 };
        unordered_map<string, pair<int, int>>hashMap;
        for (int i = points.size() - 1; i >= 0; --i) {
            for (int j = i + 1; j < points.size(); ++j) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                int g = GCA(abs(dx), abs(dy));
                dx /= g;
                dy /= g;
                bool flag = dx < 0 ^ dy < 0;
                dx = abs(dx);
                dy = abs(dy) * (flag ? -1 : 1);
                string key = getKey(i, j);
                hashMap[key] = make_pair(dx, dy);
                int cnt = 1;
                for (int k = j + 1; k < points.size(); ++k) {
                    string key = getKey(j, k);
                    auto& p = hashMap[key];
                    if (p.first == dx && p.second == dy)
                        ++cnt;
                }
                if (res[2] < cnt)
                    res = { i,j,cnt };
                else if (res[2] == cnt) {
                    if (res[0] > i || (res[0] == i && res[1] > j))
                        res = { i,j,cnt };
                }
            }
        }
        return { res[0],res[1] };
    }
};